package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-16 00:53
 */
public class Partition {

    public ListNode partition(ListNode head, int x) {

        if (head == null) return head;
        ListNode minDummy = new ListNode(0), maxDummy = new ListNode(0);
        ListNode curMax = maxDummy;
        ListNode curMin = minDummy;
        while (head != null) {
            if (head.val < x) {
                minDummy.next = head;
                minDummy = minDummy.next;
            } else {
                maxDummy.next = head;
                maxDummy = maxDummy.next;
            }
            head = head.next;
        }
        maxDummy.next=null;
        minDummy.next = curMax.next;
        return curMin.next;

    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(1);
        node1.next=node2;
        node2.next=node3;
        new Partition().partition(node1,2);
    }
}
